Exercici 7 (Tasca 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages))
Sobre la imatge dels conjunts decidibles
- Demostreu que si C \in \mathbf{RE} i f és una funció computable, aleshores f(C) \in \mathbf{RE}.
- Demostreu que la frase anterior no és certa si substituïm \mathbf{RE} per \mathbf{R}. És a dir, demostreu que existeix un conjunt C \in \mathbf{R} i una funció computable f tal que f(C) \notin \mathbf{R}.
- Demostreu que existeix un conjunt C \in \mathbf{R} i una funció computable total f tals que f(C) \notin \mathbf{R}.